package com.xj.algorithm.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 翻转二叉树
 */
public class L226_中心对称翻转二叉树 {

    /**
     * 翻转一棵二叉树。
     *
     * 示例：
     *
     * 输入：
     *
     *      4
     *    /   \
     *   2     7
     *  / \   / \
     * 1   3 6   9
     * 输出：
     *
     *      4
     *    /   \
     *   7     2
     *  / \   / \
     * 9   6 3   1
     * 备注:
     * 这个问题是受到 Max Howell 的 原问题 启发的 ：
     *
     * 谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
     */

    public static void main(String[] args) {
        TreeNode root=new TreeNode(4);
        root.left=new TreeNode(2);
        root.left.left=new TreeNode(1);
        root.left.right=new TreeNode(3);
        root.right=new TreeNode(7);
        root.right.left=new TreeNode(6);
        root.right.right=new TreeNode(9);
        System.out.println("原树如下：");
        printTree(root);

        TreeNode result=invertTreeOffice(root);
        System.out.println("调整后的树如下：");
        printTree(result);
    }


    public static void printTree(TreeNode root) {
        if(root==null){
            return ;
        }
        System.out.println(root.val);
        printTree(root.left);
        printTree(root.right);
    }

    //自己的解法；直接交换，然后处理左右子树。递归操作
    public static TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        if(root.left!=null){
            invertTree(root.left);
        }
        if(root.right!=null){
            invertTree(root.right);
        }
        return root;
    }

    //官方解法；迭代。使用队列。层次遍历。需要判断孩子节点是否为空
    public static TreeNode invertTreeOffice(TreeNode root) {
        if (root == null) return null;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            TreeNode temp = current.left;
            current.left = current.right;
            current.right = temp;
            if (current.left != null) queue.add(current.left);
            if (current.right != null) queue.add(current.right);
        }
        return root;
    }

}